We have found that Gr-1+CD11b+ cells are significantly increased in lungs of mice bearing mammary adenocarcinomas prior to tumor cell arrival. In the premetastatic lungs, these immature myeloid cells significantly decrease IFN-gamma production and increase pro-inflammatory cytokines. In addition, they produce large quantities of MMP9 and promote vascular remodeling. Deletion of MMP9 normalizes aberrant vasculature in the premetastatic lung, and diminishes lung metastasis. The production and activity of MMP9 is selectively restricted to lungs and organs with a large number of Gr-1+CD11b+ cells. Our work reveals a novel pro-tumor mechanism for Gr-1+CD11b+ cells that changes the premetastatic lung into an inflammatory and proliferative environment, diminishes immune protection and promotes metastasis through aberrant vasculature formation. Thus inhibition of Gr-1+CD11b+ cells could normalize the premetastatic lung environment, improve host immunosurveillance, and inhibit tumor metastasis.